/**  
 
*  

* @date 2018年11月21日  

*/
package com.moxi.tree;

import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.UnsupportedEncodingException;

//实现二叉排序树
public class BinarySortTree {
	/**
	 * 将文件中的内容读取出来
	 * 
	 * @date 2018年11月20日上午11:37:52
	 */
	public static String readToString(String fileName) {
		String encoding = "gbk";
		File file = new File(fileName);
		Long filelength = file.length();
		byte[] filecontent = new byte[filelength.intValue()];
		try {
			FileInputStream in = new FileInputStream(file);
			in.read(filecontent);
			in.close();
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		} catch (IOException e) {
			e.printStackTrace();
		}
		try {
			return new String(filecontent, encoding);
		} catch (UnsupportedEncodingException e) {
			System.err.println("The OS does not support " + encoding);
			e.printStackTrace();
			return null;
		}
	}

	public static void main(String[] args) {

		BinaryTree biTree = new BinaryTree();

		String text = readToString("D:\\testingdata.txt");

		// 将文本中的回车换行替换掉
		text = text.replaceAll("[\\t\\n\\r]", "");

		String[] textList = text.split("，");

		int minSum = 0;

		/**
		 * 建立二叉排序树
		 */
		for (int i = 0; i < textList.length; i++) {

			Integer key = Integer.valueOf(textList[i]);

			if (i == 0) {
				Node node = biTree.insert(key);
				minSum = key;
			} else {
				Node node = biTree.insert(key);
				minSum += node.fluctuate;
			}

		}

		System.out.println("使用二叉排序树计算");

		System.out.println("得到的最小波动值为:" + minSum);

		if (biTree.max(biTree.getRoot()) != null) {
			System.out.println("最大值:" + biTree.max(biTree.getRoot()).data);
		}

		// System.out.println("二叉树的中序遍历:");
		// biTree.inOrder();
		//
		// System.out.println();
		// System.out.println("二叉树的先序遍历:");
		// biTree.preOrder();
		// System.out.println();
		//
		// System.out.println("二叉树的后序遍历:");
		// biTree.postOrder();
		// System.out.println();
	}

}

class Node {
	public int data;
	public int fluctuate; // 波动值
	public Node left;
	public Node right;

	public Node(int val) {
		this.data = val;
		this.left = null;
		this.right = null;
		this.fluctuate = 0;
	}
}

class BinaryTree {
	private Node root;

	public BinaryTree() {
		root = null;
	}

	public Node getRoot() {
		return root;
	}

	// 将data插入到二叉排序树中
	public Node insert(int data) {
		Node newNode = new Node(data);
		Integer minNum = Integer.MAX_VALUE;
		if (root == null) {
			root = newNode;
			return newNode;
		} else {
			Node current = root;
			Node parent;
			while (true) {// 寻找插入的位置
				parent = current;

				int temp = Math.abs(data - current.data);
				if (minNum > temp) {
					minNum = temp;
				}

				if (data < current.data) {
					current = current.left;
					if (current == null) {
						newNode.fluctuate = minNum;
						parent.left = newNode;
						return newNode;
					}
				} else {
					current = current.right;
					if (current == null) {
						newNode.fluctuate = minNum;
						parent.right = newNode;
						return newNode;
					}
				}
			}

		}
	}

	// 将数值输入构建二叉树
	public void buildTree(int[] data) {
		for (int i = 0; i < data.length; i++) {
			insert(data[i]);
		}
	}

	// 中序遍历方法递归实现
	public void inOrder(Node localRoot) {
		if (localRoot != null) {
			inOrder(localRoot.left);
			System.out.print(localRoot.data + " ");
			inOrder(localRoot.right);
		}
	}

	// 寻找前驱节点，即小于该节点的最大节点
	public Node max(Node node) {
		if (node.right == null) {
			return node;
		}

		while (node.right != null) {
			node = node.right;
		}

		return node;
	}

	public void inOrder() {
		this.inOrder(this.root);
	}

	// 先序遍历方法递归实现
	public void preOrder(Node localRoot) {
		if (localRoot != null) {
			System.out.print(localRoot.data + " ");
			preOrder(localRoot.left);
			preOrder(localRoot.right);
		}
	}

	public void preOrder() {
		this.inOrder(this.root);
	}

	// 后序遍历方法递归实现
	public void postOrder(Node localRoot) {
		if (localRoot != null) {
			postOrder(localRoot.left);
			postOrder(localRoot.right);
			System.out.print(localRoot.data + " ");
		}
	}

	public void postOrder() {
		this.postOrder(this.root);
	}
}
